|
In the mathematical field of graph theory, the Nauru graph is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.〔 It has chromatic number 2, chromatic index 3, diameter 4, radius 4 and girth 6.〔Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.〕 It is also a 3-vertex-connected and 3-edge-connected graph. The Nauru graph requires at least eight crossings in any drawing of it in the plane. It is one of five non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these five graphs is the McGee graph also known as the (3-7)-cage.〔 .〕〔.〕 ==Construction== The Nauru graph is Hamiltonian and can be described by the LCF notation : ()4.〔Eppstein, D., (The many faces of the Nauru graph ) on LiveJournal, 2007.〕 The Nauru graph can also be constructed as the generalized Petersen graph ''G''(12, 5) which is formed by the vertices of an dodecagon, connected to the vertices of a twelve-point star in which each point of the star is connected to the points five steps away from it. There is also a combinatorial construction of the Nauru graph. Take three distinguishable objects and place them in four distinguishable boxes, no more than one object per box. There are 24 ways to so distribute the objects, corresponding to the 24 vertices of the graph. If it is possible to go from one state to another state by moving exactly one object from its present location to an empty box, then the vertices corresponding to the two states are joined by an edge. The resulting state-transition graph is the Nauru graph. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Nauru graph」の詳細全文を読む スポンサード リンク
|